package com.lry.basic.algorithm.stack;

import java.util.Stack;

class Find132pattern {

    // 从后往前扫描的过程中，一旦当前元素 nums[I] 比栈顶大，
    // 这个 nums[I] 或许就是我们要找的 nums[J]，弹出栈中所有的比它小的元素，
    // 这些元素就是符合条件的 nums[K],最后一个弹出的就是符合条件的最大 nums[K],
    // 如果这个 num[K] 比继续往前扫描到的 nums[I] 要大，则符合条件。


    public static void main(String[] args) {
        System.out.println(find132pattern(new int[]{3, 1, 4, 2}));
    }
    public static boolean find132pattern(int[] nums) {
        Stack<Integer> stack =  new Stack();

        int k = -1;

        for(int i=nums.length-1;i>=0;i--){
            if(k!=-1&& nums[i]<nums[k]){
                return true;
            }
            while(!stack.isEmpty()&&nums[stack.peek()] < nums[i]){
                k = stack.pop();
            }
            stack.push(i);
        }
        return false;
    }


}